package 数据结构练习;

import java.util.Scanner;

public class KMP算法 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.nextLine();
        String str2 = scanner.nextLine();
        int[] next = getNext(str2);
        System.out.print("next数组：");
        for(int x:next){
            System.out.print(x+" ");
        }
        System.out.println();
        System.out.println(kmp(str1,str2,next));
    }

    public static boolean kmp(String str1,String str2,int[] next){
        if(str1.length()<str2.length()){
            return false;
        }
        int top = 0;
        int tail = 0;
        while (top<str1.length()){
            if(str1.charAt(top) == str2.charAt(tail)){
                top++;
                tail++;
                if(tail == str2.length()-1){
                    return true;
                }
            }else if(tail == 0){
                top ++ ;
            }else {
                tail = next[tail];
            }
        }
        return false;
    }

    public static int[] getNext(String str){
        int n = str.length();
        int[] next = new int[n];
        int l=0,r=2;
        next[0] = 0;
        next[1] = 0;
        while (r<n){
            if(str.charAt(l) == str.charAt(r-1)){
                next[r] = l+1;
                l++;
                r++;
            }else if(l==0){
                next[r] = 0;
                r++;
            } else {
                l = next[l];
            }
        }
        return next;
    }
}
